#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)

// LeetCode 50. Pow(x, n)
// https://leetcode.cn/problems/powx-n/description/

class Solution {
public:
    double myPow(double x, int n)
    {
        return n < 0 ? 1 / pow(x, -(long long)n) : pow(x, n);
    }

    double pow(double x, long long n)
    {
        if (n == 0)  return 1;

        if (n % 2 == 1)
        {
            double tmp = pow(x, (n - 1) / 2);
            return tmp * tmp * x;
        }
        else
        {
            double tmp = pow(x, n / 2);
            return tmp * tmp;
        }
    }
};